class Solution {
    public List<Integer> findAnagrams0(String s, String p) {
        int sLen = s.length(), pLen = p.length();
        if (sLen < pLen) return new ArrayList<Integer>();

        List<Integer> ans = new ArrayList<Integer>();
        int[] pCount = new int[26];
        int[] sCount = new int[26];
        for (int i = 0; i<pLen;i++) {
            ++pCount[p.charAt(i) - 'a'];
            ++sCount[s.charAt(i) - 'a'];
        }

        if (Arrays.equals(sCount, pCount)) 
            ans.add(0);
        
        for (int i = 0; i < sLen - pLen; i++) {
            --sCount[s.charAt(i) - 'a'];
            ++sCount[s.charAt(i + pLen) - 'a'];

            if (Arrays.equals(sCount, pCount)) 
                ans.add(i+1);
        }

        return ans;
    }

    
    public List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();
        if (sLen < pLen) return new ArrayList<Integer>();

        List<Integer> ans = new ArrayList<Integer>();
        int[] count = new int[26];
        for (int i = 0; i<pLen;i++) {
            ++count[s.charAt(i) - 'a'];
            --count[p.charAt(i) - 'a'];
        }

        int diff = 0;
        for (int i : count){
            if (i != 0) 
                ++diff;
        }

        if (diff == 0) 
            ans.add(0);
        
        for (int i = 0; i < sLen - pLen; i++) {
            int out = s.charAt(i) - 'a';    // 要删掉字符的索引
            if (count[out] == 1) {          // 原来多一个，删掉后要变得相同了
                --diff;
            } else if (count[out] == 0) {   // 原来相同，删掉后变得不一样多了
                ++diff;
            }
            --count[out];

            
            int in = s.charAt(i + pLen) - 'a';
            if (count[in] == -1) {          // 要变得相同了
                --diff;
            } else if (count[in] == 0) { // 要变得不同了
                ++diff;
            }
            ++count[in];

            if (diff == 0) 
                ans.add(i+1);
        }

        return ans;
    }
}